package breadbox.pastry.routing;

import java.io.Serializable;
import java.util.PriorityQueue;
import java.util.Stack;

class LeafBinaryTree implements Serializable {
	private static final long serialVersionUID = -4615707015603210055L;
	private LeafBinaryNode root_;
	private LeafBinaryNode min_;
	private LeafBinaryNode max_;
	private int size_;
	
	public LeafBinaryTree( ) {
		size_ = 0;
	}
	
	public boolean isEmpty( ) {
		return root_ == null;
	}
	
	public void clear( ) {
		root_ = null;
		min_ = null;
		max_ = null;
		size_ = 0;
	}
	
	public int size( ) {
		return size_;
	}
	
	public RoutingNode max( ) {
		if( max_ != null ) {
			return max_.node;
		}
		
		return null;
	}
	
	public RoutingNode min( ) {
		if( min_ != null ) {
			return min_.node;
		}
		
		return null;
	}
	
	public boolean spans( RoutingNode n ) {
		return min( ) != null && max( ) != null && 
			min( ).compareTo( n ) <= 0 && max( ).compareTo( n ) >= 0;
	}
	
	public RoutingNode closest( RoutingNode rn ) {
		if( isEmpty( ) )
			return null;
		
		LeafBinaryNode closest = closestNode( new LeafBinaryNode( rn ) );
		
		return closest.node;
	}
	
	public void insert( RoutingNode rn ) {
		LeafBinaryNode lbn = new LeafBinaryNode( rn );
		
		if( root_ == null ) {
			root_ = lbn;
			size_++;
		} else {
			LeafBinaryNode closest = closestNode( lbn );
			
			// insert
			if( lbn.lessThan( closest ) ) {
				closest.l = lbn;
				size_++;
			} else if( lbn.greaterThan( closest ) ) {
				closest.r = lbn;
				size_++;
			}
			
			// don't insert duplicates
			/*else {
				int rand = ( new Random( ) ).nextInt( );
				
				if( rand % 2 == 0 ) {
					closest.l = lbn;
				} else {
					closest.r = lbn;
				}
			}*/
		}
		
		updateExtrema( );
	}
	
	private void updateExtrema( ) {
		// update extremes
		min_ = findMin( );
		max_ = findMax( );
	}
	
	private LeafBinaryNode findMin( ) {
		LeafBinaryNode current = root_;
		
		while( current != null && current.l != null ) {
			current = current.l;
		}
		
		return current;
	}
	
	private LeafBinaryNode findMax( ) {
		LeafBinaryNode current = root_;
		
		while( current != null && current.r != null ) {
			current = current.r;
		}
		
		return current;
	}
	
	public RoutingNode remove( RoutingNode rn ) {
		if( isEmpty( ) )
			return null;
		
		LeafBinaryNode target = new LeafBinaryNode( rn );
		LeafBinaryNode previous = null;
		LeafBinaryNode current = root_;
		LeafBinaryNode next = null;
		
		// initialize
		if( target.lessThan( current ) )
			next = current.l;
		else if( target.greaterThan( current ) )
			next = current.r;
		
		// traverse
		while( next != null ) {
			previous = current;
			current = next;
			
			if( target.lessThan( current ) )
				next = current.l;
			else if( target.greaterThan( current ) )
				next = current.r;
			else {
				next = current;
				break;
			}
		}
		
		if( !current.equals( target ) )
			return null;
		
		if( current.equals( root_ ) ) {
			if( current.l == null && current.r == null ) {
				root_ = null;
			} else if( current.l == null && current.r != null ) {
				root_ = current.r;
			} else if( current.r == null && current.l != null ) {
				root_ = current.l;
			} else {
				LeafBinaryNode least = removeMin( current.r );
				
				if( !current.r.equals( least ) ) {
					least.r = current.r;
				}
				
				root_ = least;
			}
		} else if( current.equals( previous.l ) ) {
			if( current.l == null && current.r == null ) {
				previous.l = null;
			} else if( current.l == null && current.r != null ) {
				previous.l = current.r;
			} else if( current.r == null && current.l != null ) {
				previous.l = current.l;
			} else {
				LeafBinaryNode least = removeMin( current.r );
				
				if( !current.r.equals( least ) ) {
					least.r = current.r;
				}
				
				previous.l = least;
			}
		} else if( current.equals( previous.r ) ) {
			if( current.l == null && current.r == null ) {
				previous.r = null;
			} else if( current.l == null && current.r != null ) {
				previous.r = current.r;
			} else if( current.r == null && current.l != null ) {
				previous.r = current.l;
			} else {
				LeafBinaryNode most = removeMax( current.l );
				
				if( !current.l.equals( most ) ) {
					most.l = current.l;
				}
				
				previous.r = most;
			}
		}
		
		size_--;
		updateExtrema( );
		return current.node;
	}
	
	public RoutingNode[ ] toArray( ) {
		RoutingNode[ ] r = new RoutingNode[ size_ ];
		
		Stack< LeafBinaryNode > q = new Stack< LeafBinaryNode >( );
		PriorityQueue< LeafBinaryNode > sorted = new PriorityQueue< LeafBinaryNode >( );
		
		if( root_ != null ) {
			q.push( root_ );
		}
		
		int i = 0;
		while( !q.empty( ) ) {
			LeafBinaryNode n = q.pop( );
			if( n.l != null ) {
				q.push( n.l );
			}
			
			if( n.r != null ) {
				q.push( n.r );
			}
			
//			r[ i++ ] = n.node;
			sorted.add( n );
		}
		
		while( !sorted.isEmpty( ) ) {
			LeafBinaryNode n = sorted.poll( );
			r[ i++ ] = n.node;
		}
		
		return r;
	}
	
	private LeafBinaryNode removeMin( LeafBinaryNode root ) {
		if( root == null )
			return null;
		
		LeafBinaryNode previous = root;
		LeafBinaryNode current = root.l;
		LeafBinaryNode next = null;
		
		if( current == null ) {
			return root;
		}
		
		if( current.l != null ) {
			next = current.l;
		}
		
		while( next != null ) {
			previous = current;
			current = next;
			next = next.l;
		}
		
		previous.l = current.r;
		
		return current;
	}
	
	private LeafBinaryNode removeMax( LeafBinaryNode root ) {
		if( root == null )
			return null;
		
		LeafBinaryNode previous = root;
		LeafBinaryNode current = root.r;
		LeafBinaryNode next = null;
		
		if( current == null ) {
			return root;
		}
		
		if( current.r != null ) {
			next = current.r;
		}
		
		while( next != null ) {
			previous = current;
			current = next;
			next = next.r;
		}
		
		previous.r = current.l;
		
		return current;		
	}

	private LeafBinaryNode closestNode( LeafBinaryNode target ) {
		LeafBinaryNode current = root_;
		LeafBinaryNode next;
		
		// initialize
		if( target.lessThan( current ) )
			next = current.l;
		else if( target.greaterThan( current ) )
			next = current.r;
		else {
			return current;
		}
		
		// traverse
		while( next != null ) {
			current = next;
			
			if( target.lessThan( current ) )
				next = current.l;
			else if( target.greaterThan( current ) )
				next = current.r;
			else {
				next = current;
				break;
			}
		}
		
		return current;
	}
	
	private class LeafBinaryNode implements Comparable< LeafBinaryNode >, Serializable {
		private static final long serialVersionUID = -1887825663531718511L;
		public RoutingNode node;
		public LeafBinaryNode l;
		public LeafBinaryNode r;
		
		public LeafBinaryNode( RoutingNode n ) {
			node = n;
		}
		
		public boolean lessThan( LeafBinaryNode n ) {
			return compareTo( n ) < 0;
		}
		
		public boolean greaterThan( LeafBinaryNode n ) {
			return compareTo( n ) > 0;
		}
		
		public int compareTo( LeafBinaryNode n ) {
			return node.compareTo( n.node );
		}
		
		public boolean equals( LeafBinaryNode n ) {
			return node.equals( n.node );
		}
	}
}
